The present invention relates to data storage devices employing rotating data storage media, or other data storage systems characterized by data accessing times which are appreciable in comparison with modern processing speeds (GHz). Data is transferred to, and read from, the storage medium according to commands, Ci, which specify the locations of the data on the storage medium, and also whether data is to be written on, or read from, these locations. A number of commands (typically 32, but can be 128 or more) may be stored in a command queue, from which the data storage device reads individual commands in a certain order for execution. Due to physical limits on the rotational speeds of the storage media (typically thousands of rpm) and the radial accelerations and decelerations of the read head (determining seek times), an opportunity for improving data access rates (measured in Input/Output Operations Per Second, or IOPS) presents itself in the form of algorithms for executing commands in a different order from which they were received.
One common prior art command accessing sequence is termed a “queue-depth-of one” (qd=1) rotational position ordering (RPO) native command queuing (NCQ) algorithm.
For this algorithm, the command queue is first-in-first-out (FIFO). Advantages of this method are:
                1) All commands have an absolute command completion time (CCT),        2) No commands are “lost” or substantially delayed.Unfortunately, disadvantages of this method are:        1) IOPS values tend to be lower than for non-qd=1 methods,        2) Head travel tends to be substantially increased due to typically large read head motions, potentially inducing more wear to the actuator mechanism and reduced device lifetimes or more maintenance.Thus it would be advantageous to achieve guaranteed absolute command execution times without increasing the host system workload while achieving increased IOPS. It would also be advantageous to reduce the total head travel to reduce wear on the actuator mechanism, thereby increasing device lifetimes and reducing maintenance.        